package leetcode_周赛._2022._202212;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 322 场周赛
 *
 * @author yezh
 * @date 2022/12/4 11:34
 */
public class _04 {

    /**
     * 6255. 两个城市间路径的最小分数
     * 算法：深度优先搜素
     * 从 1 开始遍历, 把所有能走到的边都遍历一遍
     */
    int ans;
    Map<Integer, List<int[]>> graph;

    public int minScore(int n, int[][] roads) {
        ans = Integer.MAX_VALUE;
        // 从 1 开始走，看能走到哪里即可，不一定要走到 n - 1
        graph = new HashMap<>(n);
        for (int[] road : roads) {
            int a = road[0], b = road[1], c = road[2];
            List<int[]> list = graph.getOrDefault(a, new ArrayList<>());
            list.add(new int[]{b, c});
            graph.put(a, list);
            list = graph.getOrDefault(b, new ArrayList<>());
            list.add(new int[]{a, c});
            graph.put(b, list);
        }
        dfs(1, new boolean[n + 1]);
        return ans;
    }

    void dfs(int start, boolean[] visited) {
        if (!graph.containsKey(start)) return;
        // 剪枝, 已经遍历过的点就不用再遍历了
        if (visited[start]) return;
        visited[start] = true;
        List<int[]> list = graph.get(start);
        for (int[] verge : list) {
            ans = Math.min(ans, verge[1]);
            dfs(verge[0], visited);
        }
    }

}
